﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GCD
{
    class gcd
    {
        /// <summary>
        /// метод евклида простой
        /// </summary>
        public static long GCDSimple(long a, long b)
        {
            long temp, c;
            if (b > a)
            { temp = a; a = b; b = temp; }
            while (b != 0)
            {
                c = a % b;
                a = b; b = c;
            }
            return a;
        }

        /// <summary>
        /// обобщенный метод евклида
        /// </summary>
        public static long[] GCDAdv(long a, long b)
        {

            const int length = 3;

            long[] row1 = new long[length] { a, 1, 0 };
            long[] row2 = new long[length] { b, 0, 1 };

            do
            {
                long[] newRow = new long[length];

                for (int i = 0; i < length; i++)
                {
                    newRow[i] = row1[i] - row2[i] * (long)(row1[0] / row2[0]);
                }
                row1 = row2;
                row2 = newRow;
            }
            while (row2[0] != 0);

            long x = row1[1];
            long y = row1[2];
            long gcd = a * x + b * y;
            if (y < 0) y += a;
            if (x < 0) x += b;
            long[] U = { gcd, x, y };
            return U;
        }
    }
}
